This invention relates to the field of digital signal processing, and more particularly to the use of filter banks for solving signal processing problems.
Subbanding is a powerful signal processing tool which can be used to help solve a wide variety of problems. The basic idea behind subbanding is to split a signal into frequency bands by means of filter banks. The processing of the signal is done within each subband. There are many different ways to design the filter banks, so many different signal decompositions are possible. Subbanding can provide new or improved signal processing techniques which can make difficult problems more tractable.
There are a number of difficult signal processing problems for which subbanding could help generate improved solutions. Some of these include blind deconvolution, echo cancellation, blind signal separation, and double-talk detection. The key to an effective implemention of subbanding is to find a filter bank which decomposes the signals in such a way that it makes the problem easier to solve. This is not a trivial task. Filter bank design has been and continues to be, an active area of research.
Echo cancellation has been used extensively in telecommunications applications to recondition a wide variety of signals, such as speech, data transmission, and video. The search for mathematical algorithms to perform echo cancellation has produced several different approaches with varying degrees of complexity, cost, and performance.
In some applications, such as the cancellation of acoustic speech echoes in hands-free phones, the echo duration can be quite long. For typical rooms the echo can range from 100 ms to 500 ms. A traditional approach to echo cancellation uses an adaptive filter of length L, where L equals the number of samples necessary to extend to just beyond the duration of the echo. Even at a telephone bit rate of 8000 samples per second, the value of L can easily be in the thousands. The computational requirements of an adaptive filter is proportional to 2L for the popular LMS (Least Mean Squares) class of algorithms, and proportional to L2 or higher for algorithms such as RLS (Recursive Mean Squares). More robust algorithms (like RLS) have greatly improved convergence characteristics over LMS methods, but the L2 computational load makes them impractical with current technology. Convergence time also increases exponentially with the size of L for most algorithms. It is important to have fast convergence, especially in the case of acoustic echo cancellation, because the echo path may be continually changing as people and objects move within the environment. An echo canceller designed to deal with an echo length of several hundred milliseconds will have problems with either computational complexity or convergence speed and accuracy.
Due to the large length of the echoes encountered in most acoustic applications, it is nearly impossible to use a single adaptive filter to perform acoustic echo cancellation. Consequently, the use of subbanding has been proposed. An adaptive filter is used to cancel the echo within each subband, and the echo-free signal is then reassembled with a synthesis filter bank. Subbanding can reduce computational complexity and result in faster, more accurate convergence. However, the application of subbanding to echo cancellation has been done with limited success because of practical difficulties, such as aliasing errors associated with the downsampling process.
When the signals are divided into M subbands, M adaptive filters are required to perform the echo cancellation. Within each subband, the signals are downsampled, that is, the sample rate is reduced. The factor by which the sample rate is reduced is typically referred to as the downsampling rate. For example, a downsampling rate of four implies that the sample rate has been reduced by a factor of four within each subband. It is important to distinguish between the downsampling rate and the sample rate. An increase in the downsampling rate results in the decrease in the sample rate.
A special case occurs when the downsampling rate equals the number of subbands (M). This is known as critical sampling, and the corresponding downsampling; rate is called the critical sampling rate. Critical sampling represents the highest amount of downsampling that is possible before signal information is lost. In this specification, reference will be made to a downsampling rate of twice the critical sampling rate. This indicates a downsampling rate equal to twice the number of subbands (2M), and a corresponding sample rate that is half as fast as critical sampling.
The length of each adaptive filter is reduced by a factor equal to the downsampling rate. The reduced sample rate allows for more time to perform computations between samples, and the shorter adaptive filters will converge with fewer iterations, and to a more accurate result. There is additional overhead from the subband filters, but there are efficient algorithms to do the subbanding. The subband filters will also introduce additional delay into the system. Provided that the subband filters are kept reasonably short, this computational overhead and additional delay will be tolerable.
With many signal processing problems, difficulties arise because existing techniques tend to provide inaccurate solutions, or they require too many computations to be economically implemented with current technology. For example, a fullband echo canceller which uses just one adaptive filter is simply not practical for the echoes typically encountered in real acoustic environments. LMS-based methods are computationally attractive, but give echo estimates which are prone to error. More accurate algorithms, like RLS, require too many computations for economical implementation. The use of subbanding allows much more accurate echo estimates to be generated for long echoes using LMS, and the computational load is reasonable. However, subbanding introduces new implementation difficulties.
There are two basic ways to perform subbanding. The direct approach involves using an M-channel filter bank to split the signal into M subbands. There are a number of problems with this method. Since ideal square filters cannot be used, there will be overlap between the subbands. This leads to aliasing errors, which become worse as the downsampling rate approaches the critical sampling rate. Lowering the downsampling rate (over-sampling) reduces aliasing, but can lead to over-determination of the problem and poor convergence. The subband filters can also introduce distortion. Filter bank theory shows that, with careful filter design, aliasing and distortion errors can be eliminated by exploiting relationships between the analysis and synthesis filters. However, these relationships are destroyed if the signals undergo processing between decomposition and reconstruction. Clearly, such processing will be necessary to cancel an echo, and so aliasing and distortion errors are inevitable.
A more recent subbanding method is wavelet decomposition. Wavelets usually exhibit orthogonality characteristics that automatically give them perfect reconstruction properties (no aliasing or distortion errors). But as with regular filter banks, these properties depend on relationships between the analysis and synthesis filters, and these relationships are destroyed by intermediate processing. Wavelet filter banks are also constructed in a tree shape, by cascading two-channel splitters and mergers. There are very fast algorithms which can implement this, but the number of subbands must therefore be a power of two. There is also less freedom when designing wavelet filter banks, since wavelet filters have to meet certain criteria that regular filter banks do not.
Distortion can be made negligible with careful filter design. But neither subbanding method can completely eliminate the overlap between subbands, so aliasing is the main problem which must be overcome. In echo cancellation, aliasing manifests itself in the form of cross-band echo. Most of the echo within a particular subband comes from the subband itself. This is known as in-band echo. Because of aliasing, some echo also comes from the other subbands. This is the cross-band echo. Reducing the downsampling rate can decrease aliasing but this diminishes the benefits of downsampling, namely the shorter filter lengths and reduced bit rate. The other option is to use cross-filters, that is, additional adaptive filters designed to eliminate cross-band echo. This increases the number of computations that need to be performed. It is highly desirable to eliminate cross-filters, since such a reduction reduces computations and simplifies the adaptive filter topology.
According to the present invention there is provided a method of processing an input signal, wherein said input signal is divided into a plurality of subbands with the aid of a bank of complex valued, single-sided subband filters, and processing takes place within said subbands.
In accordance with the principles of the invention, a filter bank has been developed which uses single-sided, subband filters, for example FIR filters, with complex filter coefficients. The single-sided frequency spectrums of the resulting subbands make aliasing negligible at near critical downsampling rates for the real case and near twice critical downsampling rate for the complex case. The filter bank is generally applicable to signal processing problems which use subbanding.
The filter bank coefficients are preferably based on the optimal least-squares approximation of a xe2x80x9cnear-idealxe2x80x9d filter whose characteristics are determined by the number of subbands and the downsampling rate.
The invention can be applied to large signal processing problems, which can be decimated using the complex subbanding approach. A particular application of the invention is to the field of echo cancelling.
An acoustic echo cancellation algorithm has been developed which uses both complex and real AIR estimates. The complex, single-sided filters are used to perform the subbanding, which eliminates the need for cross-filters.
Double-talk is detected within each subband, which tends to give better performance than fullband detection.
The invention permits arbitrary filtering blocks to be inserted between analysis and synthesis filter banks without suffering the effects of aliasing errors.
A further aspect of the invention provides a digital signal processing apparatus comprising a bank of complex-valued, single sided filters for separating an input signal into a plurality of subbands, and means for processing signals within said subbands.
The invention still further provides an echo cancellation apparatus comprising a first bank of complex-valued, single-sided subband filters to separate a remote signal into a plurality of subbands, adaptive filters generating an error estimate in each subband, a second filter bank of complex-valued, complex-valued, single-sided subband filters to separate a local signal into a plurality of subbands, a subtractor for subtracting the signal estimates from the local signal in each subband, and a third bank of single-sided subband filters to reconstitute the subbands into a composite output signal.